/**
 * 跳跃游戏 2
 *
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * 0 <= j <= nums[i]
 * i + j < n
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 *
 * 示例 1:
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 *
 * 示例 2:
 * 输入: nums = [2,3,0,1,4]
 * 输出: 2
 *
 * 提示:
 * 1 <= nums.length <= 104
 * 0 <= nums[i] <= 1000
 * 题目保证可以到达 nums[n-1]
 */

/**
 * 1. 动态规划,
 * dp[i] : 到达 i 位置的最小步数
 * 这里我们要想找到 dp[i] 的最小值, 肯定会从头再遍历一遍数组
 * 找到可以到达该位置的 dp, 然后取他们的最小值
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 *
 * 2. 贪心
 * 这题是一题典型的贪心, 我们可以从一开始的位置, 去找他所能跳的最远的位置到
 * 他现在这个位置的所有值, 因为这都是一步可以到达的, 然后我们找这个步可以到
 * 达的位置中下一次可以跳的更远的位置, 这样往复来找可以达到最远的位置
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // *********************************************
    // 贪心
    public int jump1(int[] nums) {

        // 数组长度
        int n = nums.length;

        // 这里特判一下要是 n 为 1 的话 直接放回 0
        if (n == 1) {
            return 0;
        }

        // 步数
        int step = 0;

        // tmp : 记录每个跳步时的最大值下标, max : 记录能跳到的最大下标
        int i = 0, tmp = 0, max = 0;
        while (nums[i] + i < n - 1) {

            // 这里是用来比较的, 所有每次都要置为 0
            max = 0;

            // 这里遍历能跳到的地方
            for (int j = i + 1; j <= i + nums[i]; j++) {

                // 要是能跳更远, 更新
                if (nums[j] + j > max) {
                    max = nums[j] + j;
                    tmp = j;
                }
            }

            // 这里更新下标
            i = tmp;

            // 步数加一
            step++;
        }

        // 能直接跳到结尾直接退出, 也要记得步数加 1
        step++;
        return step;
    }

    // 标准
    public int jump(int[] nums) {

        int end = 0;
        int maxPosition = 0;
        int steps = 0;

        // 这里的意思是每次都等跳到边界的时候更新步数, 然后再更新边界, 这样大大简化了每一
        // 次的循环, 降低了时间复杂度, 看着也舒服
        for(int i = 0; i < nums.length - 1; i++) {

            //找能跳的最远的
            maxPosition = Math.max(maxPosition, nums[i] + i);

            if( i == end){

                //遇到边界，就更新边界，并且步数加一
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}